// Copyright 2011, Vanya Davidenko.
// Кодировка файла: UTF-8. 
package info.iu9.red;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.assertFalse;



public class DfaInterpreterTest {
  @Before
  public void setUp() {}

  @After
  public void tearDown() {}

  @Test
  public void emptyStringAndPattern() {
    setPatternAndString("", "");
    assertTrue(match());
    assertTrue(contains());
  }

  @Test
  public void emptyString() {
    setPatternAndString("a", "");
    assertFalse(match());
    assertFalse(contains());
  }

  @Test
  public void emptyPattern() {
    setPatternAndString("", "abc");
    assertFalse(match());
    assertTrue(contains());
  }

  @Test
  public void containsOnlyBegin() {
    setPatternAndString("a", "ab");
    assertFalse(match());
    assertTrue(contains());
  }


  @Test
  public void containsOnlyMiddle() {
    setPatternAndString("b", "abc");
    assertFalse(match());
    assertTrue(contains());
  }

  @Test
  public void containsOnlyEnd() {
    setPatternAndString("c", "abc");
    assertFalse(match());
    assertTrue(contains());
  }

  @Test
  public void containsOnlyBeginWithAnchors() {
    setPatternAndString("^a", "abc");
    assertFalse(match());
    assertTrue(contains());
  }

  @Test
  public void containsOnlyEndWithAnchors() {
    setPatternAndString("c$", "abc");
    assertFalse(match());
    assertTrue(contains());
  }

  @Test
  public void matches() {
    setPatternAndString("abc", "abc");
    assertTrue(match());
    assertTrue(contains());
  }

  @Test
  public void matchesAnchored() {
    setPatternAndString("^abc$", "abc");
    assertTrue(match());
    assertTrue(contains());
  }

  @Test
  public void notContains() {
    setPatternAndString("d", "abc");
    assertFalse(match());
    assertFalse(contains());
  }

  @Test
  public void notContainsBigger() {
    setPatternAndString("abcd", "abc");
    assertFalse(match());
    assertFalse(contains());
  }

  @Test
  public void notContainsBecauseOfAnchors() {
    setPatternAndString("^a$", "abc");
    assertFalse(match());
    assertFalse(contains());
  }



  @Test
  public void cmdVisitorThenRegularVisitorBeginAnchor() {
    setPatternAndString(".*^ab", "a");
    assertFalse(match());
    assertFalse(contains());

    setPatternAndString(".*^ab", "ab");
    assertTrue(match());
    assertTrue(contains());

    setPatternAndString(".*^ab", "abc");
    assertFalse(match());
    assertTrue(contains());
  }

  @Test
  public void cmdVisitorThenRegularVisitorEndAnchor() {
    setPatternAndString("ab$.*", "a");
    assertFalse(match());
    assertFalse(contains());

    setPatternAndString("ab$.*", "ab");
    assertTrue(match());
    assertTrue(contains());

    setPatternAndString("ab$.*", "cab");
    assertFalse(match());
    assertTrue(contains());
  }


  public void cmdVisitorThenRegularVisitorBugTests() {
    // Эти тесты по очередности долго не работали из-за неправильной
    // последовательности действий:
    //   - переход к следующему символу
    //   - переход по состояниям-командам (эпсилон-переходы)
    //   - переход по состояниям-символам.

    setPatternAndString("a$.*", "ab");
    assertFalse(match());
    assertFalse(contains());

    setPatternAndString(".*^a", "ba");  // этот тест долгое время не работал
    assertFalse(match());
    assertFalse(contains());
  }




  @Test
  public void searchEmpty() {
    setPatternAndString("", "abc");
    assertEquals("", search());
  }

  @Test
  public void searchFirstDot() {
    setPatternAndString(".", "abc");
    assertEquals("a", search());
  }

  @Test
  public void searchFirstDoubleDot() {
    setPatternAndString("..", "abc");
    assertEquals("ab", search());
  }

  @Test
  public void searchCharacterGroup() {
    setPatternAndString("[a-z]", "abc");
    assertEquals("a", search());
  }

  @Test
  public void searchCharacterGroupAndDot() {
    setPatternAndString("[a-c].", "abc");
    assertEquals("ab", search());
  }


  @Test
  public void searchBegin() {
    setPatternAndString("ab", "abc");
    assertEquals("ab", search());
  }

  @Test
  public void searchBeginOneLetter() {
    setPatternAndString("a", "abc");
    assertEquals("a", search());
  }

  @Test
  public void searchMiddle() {
    setPatternAndString("bc", "abcd");
    assertEquals("bc", search());
  }

  @Test
  public void searchMiddleOneLetter() {
    setPatternAndString("b", "abcd");
    assertEquals("b", search());
  }

  @Test
  public void searchEnd() {
    setPatternAndString("bc", "abc");
    assertEquals("bc", search());
  }

  @Test
  public void searchEndOneLetter() {
    setPatternAndString("c", "abc");
    assertEquals("c", search());
  }

  @Test
  public void searchBiggerRight() {
    setPatternAndString("abcd", "abc");
    assertEquals(null, search());
  }

  @Test
  public void searchBiggerLeft() {
    setPatternAndString("xabc", "abc");
    assertEquals(null, search());
  }

  @Test
  public void searchSomethingElse() {
    setPatternAndString("x", "abc");
    assertEquals(null, search());
  }

  @Test
  public void searchSomethingElseCharacterGroup() {
    setPatternAndString("[x-z]", "abc");
    assertEquals(null, search());
  }


  @Test
  public void searchBeginAnchorsFlip() {
    setPatternAndString("^ab.", "abc");
    assertEquals("abc", search());

    setPatternAndString("^ab.", "\nabc");
    assertEquals(null, search());
  }

  @Test
  public void searchEndAnchorsFlip() {
    setPatternAndString("ab.$", "abc\nabd");
    assertEquals("abd", search());

    setPatternAndString("ab.$", "abc\nabd\n");
    assertEquals("abd", search());

    setPatternAndString("ab.$", "abc\nabd\n\n");

    assertEquals(null, search());
  }

  @Test
  public void searchBeginEndAnchorsFlipMultiline() {
    setPatternAndString("(?m:^a.c$)", "axcd\naycx\n azc\nabc\n");
    assertEquals("abc", search());

    // Несколько тестов из-за того, что когда Dfa запускает обратный ход,
    // то несмотря на то, что он идет по некоторому срезу строки, ему должны
    // быть доступны все символы, для проверки якорей:
    // паттерн: (?m:a$) строка a\nx, $ сработал как multiline из-за \n,
    // и хотя 1-го символа строка ('\n') не присутствует в срезе, доступ к нему
    // необходим для проверки якоря на обратном шаге.
    setPatternAndString("(?m:^a.c$)", "\n\nabc\n\n");
    assertEquals("abc", search());

    setPatternAndString("(?m:^a.c$)", "\nabc\n");
    assertEquals("abc", search());

    setPatternAndString("(?m:^a.c$)", "abc\n");
    assertEquals("abc", search());

    setPatternAndString("(?m:^a.c$)", "\nabc");
    assertEquals("abc", search());

    setPatternAndString("(?m:^a.c$)", "abc");
    assertEquals("abc", search());
  }

  @Test
  public void searchBeginEndAnchorsFlipAZ() {
    setPatternAndString("(?sn:\\Aa\\Z)", "a");
    assertEquals("a", search());

    setPatternAndString("(?sn:\\Aa\\Z)", "a\n");
    assertEquals("a", search());

    setPatternAndString("(?sn:\\Aa\n\\Z)", "a\n");
    assertEquals("a\n", search());

    setPatternAndString("(?sn:\\Aa\\Z)", "a\n\n");
    assertEquals(null, search());

    setPatternAndString("(?sn:\\Aa\\Z)", "\na");
    assertEquals(null, search());
  }

  @Test
  public void searchBeginEndAnchorsFlipAz() {
    setPatternAndString("(?sn:\\Aa.c\\z)", "a\nc");
    assertEquals("a\nc", search());

    setPatternAndString("(?sn:\\Aa.c\\z)", "a\nc\n");
    assertEquals(null, search());
  }

  @Test
  public void searchWordBoundaryAnchor() {
    setPatternAndString("\\Bab.", "abc abd xabe");
    assertEquals("abe", search());
  }

  @Test
  public void searchInvertedWordBoundaryAnchor() {
    setPatternAndString("ab\\b.", "abc ab ");
    assertEquals("ab ", search());

    setPatternAndString("\\bab.", "abc ab ");
    assertEquals("abc", search());
  }


  @Test
  public void searchAlternative() {
    setPatternAndString("xb|ab", "xaby");
    assertEquals("ab", search());

    setPatternAndString("ab|ax", "xaby");
    assertEquals("ab", search());
  }

  @Test
  public void searchAlternativeMany() {
    setPatternAndString(".|a|b|y", "xaby");
    assertEquals("x", search());

    setPatternAndString("(xb)|(abz)|(by)|(aby)", "xaby");
    assertEquals("aby", search());
  }

  @Test
  public void searchAlternativeWithRepeats() {
    setPatternAndString("(a(bc)+.)|abc|b|c", "abcbcx");
    assertEquals("abcbcx", search());

    setPatternAndString("(a|b|c)+|(abc)+", "xaabc");
    assertEquals("aabc", search());
  }

  public void searchAlternativeLotsOfQuntifiers() {
    setPatternAndString("((a*b)+)?", "baabaaabb");
    assertEquals("baabaaabb", search());
  }


  @Test
  public void searchAlternativeWithEmpty() {
    setPatternAndString("^|x", "xab");
    assertEquals("", search());

    setPatternAndString("x|^", "xab");
    assertEquals("x", search());
  }

  @Test
  public void searchZeroOrOne() {
    setPatternAndString("b(a.)?", "baaa aa");
    assertEquals("baa", search());

    setPatternAndString("b(a.)??", "baaa aa");
    assertEquals("b", search());
  }

  @Test
  public void searchZeroOrMany() {
    setPatternAndString("<.*>", "<a>tag</a>");
    assertEquals("<a>tag</a>", search());

    setPatternAndString("<.*?>", "<a>tag</a>");
    assertEquals("<a>", search());
  }

  @Test
  public void searchOneOrMany() {
    setPatternAndString("a+", "baaa aa");
    assertEquals("aaa", search());

    setPatternAndString("a+?", "baaabaa");
    assertEquals("a", search());


    setPatternAndString("<.+>", "_<a>tag</a>_");
    assertEquals("<a>tag</a>", search());

    setPatternAndString("<.+?>", "_<a>tag</a>_");
    assertEquals("<a>", search());
  }

  @Test
  public void searchGoogleWithManyForks() {
    setPatternAndString("\\b[Gg]?(a|o+)*?g{0,5}(le)+\\b", "re2 by google");
    assertEquals("google", search());
  }

  @Test
  public void searchReverseStringNotCut() {
    setPatternAndString("(a|..$)", "ca\nx");
    assertEquals("a", search());

    setPatternAndString("(..$|a)", "ca\nx");  // $ != ^ML в обратном ходе
    assertEquals("a", search());
  }

  @Test
  public void searchAlternativeWithSimilarReturnPaths() {
    setPatternAndString("(x|k)*(ab|cb)", "xkcb");
    assertEquals("xkcb", search());
  }

  @Test
  public void searchAlternativeWithEqualReturnPaths() {
    setPatternAndString("(x|k)*(k.b|cb)", "xkcb");
    assertEquals("xkcb", search());
  }

 @Test
  public void searchAlternativeWithFakeReturnPath() {
    setPatternAndString("x(.*|kcb)", "xkcb");
    assertEquals("xkcb", search());
  }

  @Test
  public void searchAlternativePriorityCheck() {
    setPatternAndString("(^|\n*)", "\n\n\n");
    assertEquals("", search());

    setPatternAndString("(\n*|^)", "\n\n\n");
    assertEquals("\n\n\n", search());
  }

  @Test
  public void searchAlternativeLazyPriorityCheck() {
    setPatternAndString("(a*?|aaa)", "aaaa");
    assertEquals("", search());

    setPatternAndString("(a*?$|aaa)", "aaaa");
    assertEquals("aaaa", search());
  }


  @Test
  public void searchFirstTests() {
    // Самые базовые тесты алгоритма переворачивания автомата.
    setPatternAndString("a*", "aaaa");
    assertEquals("aaaa", search());

    setPatternAndString("a*?", "aaaa");
    assertEquals("", search());

    setPatternAndString("ax*b", "yabz");
    assertEquals("ab", search());

    setPatternAndString("a(xy)*?b", "axyb");
    assertEquals("axyb", search());

    setPatternAndString("((a*)b)+", "abbbbba");
    assertEquals("abbbbb", search());


    setPatternAndString("a?b", "bbbbba");
    assertEquals("b", search());

    setPatternAndString("x(ab)?y", "xy");
    assertEquals("xy", search());

    setPatternAndString("x(a*)?y", "xaaay");
    assertEquals("xaaay", search());


    setPatternAndString("x|y", "xy");
    assertEquals("x", search());

    setPatternAndString("y|x", "xy");
    assertEquals("x", search());

    setPatternAndString("a(x|y)", "zayz");
    assertEquals("ay", search());

    setPatternAndString("ax|y", "zayz");
    assertEquals("y", search());

    setPatternAndString("x|y|z", "abcyzxc");
    assertEquals("y", search());

    setPatternAndString("(xy)|(ab)|(12)", "xxxx12abab");
    assertEquals("12", search());

    setPatternAndString("x+|yy*|zz?", "aaaxxxyyayyzzz");
    assertEquals("xxx", search());
  }


  @Test
  public void simpleUtf16SurrogateTest() {
    setPatternAndString("((\uD834\uDD1E)|u|\u6C34)+", "\uD834\uDD1E");
    assertEquals("\uD834\uDD1E", search());

    setPatternAndString("(.|u|\u6C34)+", "\uD834\uDD1E");
    assertEquals("\uD834\uDD1E", search());
  }

  @Test(expected = StringIndexOutOfBoundsException.class)
  public void invalidUtf16StringTest() {
    setPatternAndString("(\uD834|u|\u6C34)+", "\uD834");
    search();
  }



  private void setPatternAndString(final String pattern, final String string) {
    final FiniteAutomata fa = new Parser(pattern).parse();
    final FiniteAutomataAnalyzer faa = new FiniteAutomataAnalyzer(fa);

    dfa_interpreter_ = new DfaInterpreter(fa,
                                          faa.fact_map(),
                                          faa.max_fact_num());
    string_ = string;
  }

  private boolean contains() {
    return dfa_interpreter_.contains(string_);
  }

  private boolean match() {
    return dfa_interpreter_.matches(string_);
  }

  private String search() {
    final Submatch r = dfa_interpreter_.search(string_);
    if ( r == null ) {
      return null;
    }
    return r.toString();
  }

  private DfaInterpreter dfa_interpreter_;
  private String string_;
}
